Data storage devices may use a forward map, such as a forward map searchable in O(log n) time or faster, to relate logical addresses to physical locations on a storage tier for use by a host device. Depending on the sizes of the logical and physical address ranges and the level of fragmentation of the data on the storage media, data structures representing the forward map, such as a tree or hash table, may grow too large for available memory space. Size of the data structure representing the forward map is more likely to be problematic on individual storage devices with limited memory space and dynamic storage tiers that may require frequent updates to the forward map.